home *** CD-ROM | disk | FTP | other *** search
/ CD Actual 85 / CD Temático 40 Febrero 2004.iso / DOS / ntfs / common / super.c < prev    next >
Encoding:
C/C++ Source or Header  |  2001-02-11  |  14.0 KB  |  573 lines
  1. /*
  2.  *  super.c
  3.  *
  4.  *  Copyright (C) 1995-1997, 1999 Martin von L÷wis
  5.  *  Copyright (C) 1996-1997 RΘgis Duchesne
  6.  *  Copyright (C) 1999 Steve Dodd
  7.  */
  8.  
  9. #include "ntfstypes.h"
  10. #include "struct.h"
  11. #include "super.h"
  12.  
  13. #include <errno.h>
  14. #include "macros.h"
  15. #include "inode.h"
  16. #include "support.h"
  17. #include "util.h"
  18.  
  19. /*
  20.  * All important structures in NTFS use 2 consistency checks :
  21.  * . a magic structure identifier (FILE, INDX, RSTR, RCRD...)
  22.  * . a fixup technique : the last word of each sector (called a fixup) of a
  23.  *   structure's record should end with the word at offset <n> of the first
  24.  *   sector, and if it is the case, must be replaced with the words following
  25.  *   <n>. The value of <n> and the number of fixups is taken from the fields
  26.  *   at the offsets 4 and 6.
  27.  *
  28.  * This function perform these 2 checks, and _fails_ if :
  29.  * . the magic identifier is wrong
  30.  * . the size is given and does not match the number of sectors
  31.  * . a fixup is invalid
  32.  */
  33. int ntfs_fixup_record(ntfs_volume *vol, char *record, char *magic, int size)
  34. {
  35.     int start, count, offset;
  36.     ntfs_u16 fixup;
  37.  
  38.     if(!IS_MAGIC(record,magic))
  39.         return 0;
  40.     start=NTFS_GETU16(record+4);
  41.     count=NTFS_GETU16(record+6);
  42.     count--;
  43.     if(size && vol->blocksize*count != size)
  44.         return 0;
  45.     fixup = NTFS_GETU16(record+start);
  46.     start+=2;
  47.     offset=vol->blocksize-2;
  48.     while(count--){
  49.         if(NTFS_GETU16(record+offset)!=fixup)
  50.             return 0;
  51.         NTFS_PUTU16(record+offset, NTFS_GETU16(record+start));
  52.         start+=2;
  53.         offset+=vol->blocksize;
  54.     }
  55.     return 1;
  56. }
  57.  
  58. /* Get vital informations about the ntfs partition from the boot sector */
  59. int ntfs_init_volume(ntfs_volume *vol,char *boot)
  60. {
  61.     /* Historical default values, in case we don't load $AttrDef */
  62.     vol->at_standard_information=0x10;
  63.     vol->at_attribute_list=0x20;
  64.     vol->at_file_name=0x30;
  65.     vol->at_security_descriptor=0x50;
  66.     vol->at_data=0x80;
  67.     vol->at_index_root=0x90;
  68.     vol->at_index_allocation=0xA0;
  69.     vol->at_bitmap=0xB0;
  70.     vol->at_symlink=0xC0;
  71.  
  72.     /* Sector size */
  73.     vol->blocksize=NTFS_GETU16(boot+0xB);
  74.     vol->clusterfactor=NTFS_GETU8(boot+0xD);
  75.     vol->mft_clusters_per_record=NTFS_GETS8(boot+0x40);
  76.     vol->index_clusters_per_record=NTFS_GETS8(boot+0x44);
  77.     
  78.     /* Just some consistency checks */
  79.     if(NTFS_GETU32(boot+0x40)>256)
  80.         ntfs_error("Unexpected data #1 in boot block\n");
  81.     if(NTFS_GETU32(boot+0x44)>256)
  82.         ntfs_error("Unexpected data #2 in boot block\n");
  83.     if(vol->index_clusters_per_record<0){
  84.         ntfs_error("Unexpected data #3 in boot block\n");
  85.         /* If this really means a fraction, setting it to 1
  86.            should be safe. */
  87.         vol->index_clusters_per_record=1;
  88.     }
  89.     /* in some cases, 0xF6 meant 1024 bytes. Other strange values have not
  90.        been observed */
  91.     if(vol->mft_clusters_per_record<0 && vol->mft_clusters_per_record!=-10)
  92.         ntfs_error("Unexpected data #4 in boot block\n");
  93.  
  94.     vol->clustersize=vol->blocksize*vol->clusterfactor;
  95.     if(vol->mft_clusters_per_record>0)
  96.         vol->mft_recordsize=
  97.             vol->clustersize*vol->mft_clusters_per_record;
  98.     else
  99.         vol->mft_recordsize=1<<(-vol->mft_clusters_per_record);
  100.     vol->index_recordsize=vol->clustersize*vol->index_clusters_per_record;
  101.     /* FIXME: long long value */
  102.     vol->mft_cluster=NTFS_GETU64(boot+0x30);
  103.  
  104.     /* This will be initialized later */
  105.     vol->upcase=0;
  106.     vol->upcase_length=0;
  107.     vol->mft_ino=0;
  108.     return 0;
  109. }
  110.  
  111. static void 
  112. ntfs_init_upcase(ntfs_inode *upcase)
  113. {
  114.     ntfs_io io;
  115. #define UPCASE_LENGTH  256
  116.     upcase->vol->upcase = ntfs_malloc(2*UPCASE_LENGTH);
  117.     if( !upcase->vol->upcase )
  118.         return;
  119.     io.fn_put=ntfs_put;
  120.     io.fn_get=0;
  121.     io.param=(char*)upcase->vol->upcase;
  122.     io.size=2*UPCASE_LENGTH;
  123.     ntfs_read_attr(upcase,upcase->vol->at_data,0,0,&io);
  124.     upcase->vol->upcase_length = io.size;
  125. }
  126.  
  127. static int
  128. process_attrdef(ntfs_inode* attrdef,ntfs_u8* def)
  129. {
  130.     int type = NTFS_GETU32(def+0x80);
  131.     int check_type = 0;
  132.     ntfs_volume *vol=attrdef->vol;
  133.     ntfs_u16* name = (ntfs_u16*)def;
  134.  
  135.     if(ntfs_ua_strncmp(name,"$STANDARD_INFORMATION",64)==0){
  136.         vol->at_standard_information=type;
  137.         check_type=0x10;
  138.     }else if(ntfs_ua_strncmp(name,"$ATTRIBUTE_LIST",64)==0){
  139.         vol->at_attribute_list=type;
  140.         check_type=0x20;
  141.     }else if(ntfs_ua_strncmp(name,"$FILE_NAME",64)==0){
  142.         vol->at_file_name=type;
  143.         check_type=0x30;
  144.     }else if(ntfs_ua_strncmp(name,"$SECURITY_DESCRIPTOR",64)==0){
  145.         vol->at_file_name=type;
  146.     }else if(ntfs_ua_strncmp(name,"$DATA",64)==0){
  147.         vol->at_data=type;
  148.         check_type=0x80;
  149.     }else if(ntfs_ua_strncmp(name,"$INDEX_ROOT",64)==0){
  150.         vol->at_index_root=type;
  151.         check_type=0x90;
  152.     }else if(ntfs_ua_strncmp(name,"$INDEX_ALLOCATION",64)==0){
  153.         vol->at_index_allocation=type;
  154.         check_type=0xA0;
  155.     }else if(ntfs_ua_strncmp(name,"$BITMAP",64)==0){
  156.         vol->at_bitmap=type;
  157.         check_type=0xB0;
  158.     }else if(ntfs_ua_strncmp(name,"$SYMBOLIC_LINK",64)==0 ||
  159.          ntfs_ua_strncmp(name,"$REPARSE_POINT",64)==0){
  160.         vol->at_symlink=type;
  161.     }
  162.     if(check_type && check_type!=type){
  163.         ntfs_error("Unexpected type %x for %x\n",type,check_type);
  164.         return EINVAL;
  165.     }
  166.     return 0;
  167. }
  168.  
  169. int
  170. ntfs_init_attrdef(ntfs_inode* attrdef)
  171. {
  172.     ntfs_u8 *buf;
  173.     ntfs_io io;
  174.     int offset,error,i;
  175.     ntfs_attribute *data;
  176.     buf=ntfs_malloc(4050); /* 90*45 */
  177.     if(!buf)return ENOMEM;
  178.     io.fn_put=ntfs_put;
  179.     io.fn_get=ntfs_get;
  180.     io.do_read=1;
  181.     offset=0;
  182.     data=ntfs_find_attr(attrdef,attrdef->vol->at_data,0);
  183.     if(!data){
  184.         ntfs_free(buf);
  185.         return EINVAL;
  186.     }
  187.     do{
  188.         io.param=buf;
  189.         io.size=4050;
  190.         error=ntfs_readwrite_attr(attrdef,data,offset,&io);
  191.         for(i=0;!error && i<io.size-0xA0;i+=0xA0)
  192.             error=process_attrdef(attrdef,buf+i);
  193.         offset+=4096;
  194.     }while(!error && io.size);
  195.     ntfs_free(buf);
  196.     return error;
  197. }
  198.  
  199. int ntfs_load_special_files(ntfs_volume *vol)
  200. {
  201.     int error;
  202.     ntfs_inode upcase,attrdef;
  203.  
  204.     vol->mft_ino=(ntfs_inode*)ntfs_calloc(3*sizeof(ntfs_inode));
  205.     error=ENOMEM;
  206.     ntfs_debug(DEBUG_BSD,"Going to load MFT\n");
  207.     if(!vol->mft_ino || (error=ntfs_init_inode(vol->mft_ino,vol,FILE_MFT)))
  208.     {
  209.         ntfs_error("Problem loading MFT\n");
  210.         return error;
  211.     }
  212.     ntfs_debug(DEBUG_BSD,"Going to load MIRR\n");
  213.     vol->mftmirr=vol->mft_ino+1;
  214.     if((error=ntfs_init_inode(vol->mftmirr,vol,FILE_MFTMIRR))){
  215.         ntfs_error("Problem %d loading MFTMirr\n",error);
  216.         return error;
  217.     }
  218.     ntfs_debug(DEBUG_BSD,"Going to load BITMAP\n");
  219.     vol->bitmap=vol->mft_ino+2;
  220.     if((error=ntfs_init_inode(vol->bitmap,vol,FILE_BITMAP))){
  221.         ntfs_error("Problem loading Bitmap\n");
  222.         return error;
  223.     }
  224.     ntfs_debug(DEBUG_BSD,"Going to load UPCASE\n");
  225.     error=ntfs_init_inode(&upcase,vol,FILE_UPCASE);
  226.     if(error)return error;
  227.     ntfs_init_upcase(&upcase);
  228.     ntfs_clear_inode(&upcase);
  229.     ntfs_debug(DEBUG_BSD,"Going to load ATTRDEF\n");
  230.     error=ntfs_init_inode(&attrdef,vol,FILE_ATTRDEF);
  231.     if(error)return error;
  232.     error=ntfs_init_attrdef(&attrdef);
  233.     ntfs_clear_inode(&attrdef);
  234.     if(error)return error;
  235.     return 0;
  236. }
  237.  
  238. int ntfs_release_volume(ntfs_volume *vol)
  239. {
  240.     if(vol->mft_ino){
  241.         ntfs_clear_inode(vol->mft_ino);
  242.         ntfs_clear_inode(vol->mftmirr);
  243.         ntfs_clear_inode(vol->bitmap);
  244.         ntfs_free(vol->mft_ino);
  245.         vol->mft_ino=0;
  246.     }
  247.     ntfs_free(vol->mft);
  248.     ntfs_free(vol->upcase);
  249.     return 0;
  250. }
  251.  
  252. /*
  253.  * Writes the volume size into vol_size. Returns 0 if successful
  254.  * or error.
  255.  */
  256. int ntfs_get_volumesize(ntfs_volume *vol, long *vol_size )
  257. {
  258.     ntfs_io io;
  259.     ntfs_u64 size;
  260.     char *cluster0;
  261.  
  262.     if( !vol_size )
  263.         return EFAULT;
  264.  
  265.     cluster0=ntfs_malloc(vol->clustersize);
  266.     if( !cluster0 )
  267.         return ENOMEM;
  268.  
  269.     io.fn_put=ntfs_put;
  270.     io.fn_get=ntfs_get;
  271.     io.param=cluster0;
  272.     io.do_read=1;
  273.     io.size=vol->clustersize;
  274.     ntfs_getput_clusters(vol,0,0,&io);
  275.     size=NTFS_GETU64(cluster0+0x28);
  276.     ntfs_free(cluster0);
  277.     /* FIXME: more than 2**32 cluster */
  278.     /* FIXME: gcc will emit udivdi3 if we don't truncate it */
  279.     *vol_size = ((unsigned long)size)/vol->clusterfactor;
  280.     return 0;
  281. }
  282.  
  283. static int nc[16]={4,3,3,2,3,2,2,1,3,2,2,1,2,1,1,0};
  284.  
  285. int 
  286. ntfs_get_free_cluster_count(ntfs_inode *bitmap)
  287. {
  288.     unsigned char bits[2048];
  289.     int offset,error;
  290.     int clusters=0;
  291.     ntfs_io io;
  292.  
  293.     offset=0;
  294.     io.fn_put=ntfs_put;
  295.     io.fn_get=ntfs_get;
  296.     while(1)
  297.     {
  298.         register int i;
  299.         io.param=bits;
  300.         io.size=2048;
  301.         error=ntfs_read_attr(bitmap,bitmap->vol->at_data,0,
  302.                      offset,&io);
  303.         if(error || io.size==0)break;
  304.         /* I never thought I would do loop unrolling some day */
  305.         for(i=0;i<io.size-8;){
  306.             clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
  307.             clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
  308.             clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
  309.             clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
  310.             clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
  311.             clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
  312.             clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
  313.             clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
  314.         }
  315.         for(;i<io.size;){
  316.             clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
  317.         }
  318.         offset+=io.size;
  319.     }
  320.     return clusters;
  321. }
  322.  
  323. /* Insert the fixups for the record. The number and location of the fixes 
  324.    is obtained from the record header */
  325. void ntfs_insert_fixups(unsigned char *rec, int secsize)
  326. {
  327.     int first=NTFS_GETU16(rec+4);
  328.     int count=NTFS_GETU16(rec+6);
  329.     int offset=-2;
  330.     ntfs_u16 fix=NTFS_GETU16(rec+first);
  331.     fix=fix+1;
  332.     NTFS_PUTU16(rec+first,fix);
  333.     count--;
  334.     while(count--){
  335.         first+=2;
  336.         offset+=secsize;
  337.         NTFS_PUTU16(rec+first,NTFS_GETU16(rec+offset));
  338.         NTFS_PUTU16(rec+offset,fix);
  339.     };
  340. }
  341.  
  342. /* search the bitmap bits of l bytes for *cnt zero bits. Return the bit
  343.    number in *loc, which is initially set to the number of the first bit.
  344.    Return the largest block found in *cnt. Return 0 on success, ENOSPC if
  345.    all bits are used */
  346. static int 
  347. search_bits(unsigned char* bits,ntfs_cluster_t *loc,int *cnt,int l)
  348. {
  349.     unsigned char c=0;
  350.     int bc=0;
  351.     int bstart=0,bstop=0,found=0;
  352.     int start,stop=0,in=0;
  353.     /* special case searching for a single block */
  354.     if(*cnt==1){
  355.         while(l && *bits==0xFF){
  356.             bits++;
  357.             *loc+=8;
  358.             l--;
  359.         }
  360.         if(!l)return ENOSPC;
  361.         for(c=*bits;c & 1;c>>=1)
  362.             (*loc)++;
  363.         return 0;
  364.     }
  365.     start=*loc;
  366.     while(l || bc){
  367.         if(bc==0){
  368.             c=*bits;
  369.             if(l){
  370.                 l--;bits++;
  371.             }
  372.             bc=8;
  373.         }
  374.         if(in){
  375.             if((c&1)==0)
  376.                 stop++;
  377.             else{ /* end of sequence of zeroes */
  378.                 in=0;
  379.                 if(!found || bstop-bstart<stop-start){
  380.                     bstop=stop;bstart=start;found=1;
  381.                     if(bstop-bstart>*cnt)
  382.                         break;
  383.                 }
  384.                 start=stop+1;
  385.             }
  386.         }else{
  387.             if(c&1)
  388.                 start++;
  389.             else{ /*start of sequence*/
  390.                 in=1;
  391.                 stop=start+1;
  392.             }
  393.         }
  394.         bc--;
  395.         c>>=1;
  396.     }
  397.     if(in && (!found || bstop-bstart<stop-start)){
  398.         bstop=stop;bstart=start;found=1;
  399.     }
  400.     if(!found)return ENOSPC;
  401.     *loc=bstart;
  402.     if(*cnt>bstop-bstart)
  403.         *cnt=bstop-bstart;
  404.     return 0;
  405. }
  406.  
  407. int 
  408. ntfs_set_bitrange(ntfs_inode* bitmap,ntfs_cluster_t loc,int cnt,int bit)
  409. {
  410.     int bsize,locit,error;
  411.     unsigned char *bits,*it;
  412.     ntfs_io io;
  413.  
  414.     io.fn_put=ntfs_put;
  415.     io.fn_get=ntfs_get;
  416.     bsize=(cnt+(loc & 7)+7) >> 3; /* round up to multiple of 8*/
  417.     bits=ntfs_malloc(bsize);
  418.     io.param=bits;
  419.     io.size=bsize;
  420.     if(!bits)
  421.         return ENOMEM;
  422.     error=ntfs_read_attr(bitmap,bitmap->vol->at_data,0,loc>>3,&io);
  423.     if(error || io.size!=bsize){
  424.         ntfs_free(bits);
  425.         return error?error:EIO;
  426.     }
  427.     /* now set the bits */
  428.     it=bits;
  429.     locit=loc;
  430.     while(locit%8 && cnt){ /* process first byte */
  431.         if(bit)
  432.             *it |= 1<<(locit%8);
  433.         else
  434.             *it &= ~(1<<(locit%8));
  435.         cnt--;locit++;
  436.         if(locit%8==0)
  437.             it++;
  438.     }
  439.     while(cnt>8){ /*process full bytes */
  440.         *it= bit ? 0xFF : 0;
  441.         cnt-=8;
  442.         locit+=8;
  443.         it++;
  444.     }
  445.     while(cnt){ /*process last byte */
  446.         if(bit)
  447.             *it |= 1<<(locit%8);
  448.         else
  449.             *it &= ~(1<<(locit%8));
  450.         cnt--;locit++;
  451.     }
  452.     /* reset to start */
  453.     io.param=bits;
  454.     io.size=bsize;
  455.     error=ntfs_write_attr(bitmap,bitmap->vol->at_data,0,loc>>3,&io);
  456.     ntfs_free(bits);
  457.     if(error)return error;
  458.     if(io.size!=bsize)
  459.         return EIO;
  460.     return 0;
  461. }
  462.   
  463.   
  464.     
  465. /* allocate count clusters around location. If location is -1,
  466.    it does not matter where the clusters are. Result is 0 if
  467.    success, in which case location and count says what they really got */
  468. int 
  469. ntfs_search_bits(ntfs_inode* bitmap, ntfs_cluster_t *location, int *count, int flags)
  470. {
  471.     unsigned char *bits;
  472.     ntfs_io io;
  473.     int error=0,found=0;
  474.     int cnt,bloc=-1,bcnt=0;
  475.     int start;
  476.     ntfs_cluster_t loc;
  477.  
  478.     bits=ntfs_malloc(2048);
  479.     if( !bits )
  480.         return ENOMEM;
  481.     io.fn_put=ntfs_put;
  482.     io.fn_get=ntfs_get;
  483.     io.param=bits;
  484.  
  485.     /* first search within +/- 8192 clusters */
  486.     start=*location>>3;
  487.     start= start>1024 ? start-1024 : 0;
  488.     io.size=2048;
  489.     error=ntfs_read_attr(bitmap,bitmap->vol->at_data,0,start,&io);
  490.     if(error)goto fail;
  491.     loc=start*8;
  492.     cnt=*count;
  493.     error=search_bits(bits,&loc,&cnt,io.size);
  494.     if(error)
  495.         goto fail;
  496.     if(*count==cnt){
  497.         bloc=loc;
  498.         bcnt=cnt;
  499.         goto success;
  500.     }
  501.  
  502.     /* now search from the beginning */
  503.     for(start=0;1;start+=2048)
  504.     {
  505.         io.param=bits;
  506.         io.size=2048;
  507.         error=ntfs_read_attr(bitmap,bitmap->vol->at_data,
  508.                      0,start,&io);
  509.         if(error)goto fail;
  510.         if(io.size==0){
  511.             if(found)
  512.                 goto success;
  513.             else{
  514.                 error=ENOSPC;
  515.                 goto fail;
  516.             }
  517.         }
  518.         loc=start*8;
  519.         cnt=*count;
  520.         error=search_bits(bits,&loc,&cnt,io.size);
  521.         if(error)
  522.             goto fail;
  523.         if(*count==cnt)
  524.             goto success;
  525.         if(bcnt<cnt){
  526.             bcnt=cnt;
  527.             bloc=loc;
  528.             found=1;
  529.         }
  530.     }
  531.  success:
  532.     ntfs_free(bits);
  533.     /* check flags */
  534.     if((flags & ALLOC_REQUIRE_LOCATION) && *location!=bloc)
  535.         error=ENOSPC;
  536.     else if((flags & ALLOC_REQUIRE_SIZE) && *count!=bcnt)
  537.         error=ENOSPC;
  538.     else ntfs_set_bitrange(bitmap,bloc,bcnt,1);
  539.     /* If allocation failed due to the flags, tell the caller what he
  540.        could have gotten */
  541.     *location=bloc;
  542.     *count=bcnt;
  543.     return 0;
  544.  fail:
  545.     *location=-1;
  546.     *count=0;
  547.     ntfs_free(bits);
  548.     return error;
  549. }
  550.  
  551. int ntfs_allocate_clusters(ntfs_volume *vol, ntfs_cluster_t *location, int *count,
  552.     int flags)
  553. {
  554.     int error;
  555.     error=ntfs_search_bits(vol->bitmap,location,count,flags);
  556.     return error;
  557. }
  558.  
  559. int ntfs_deallocate_clusters(ntfs_volume *vol, ntfs_cluster_t location, int count)
  560. {
  561.     int error;
  562.     error=ntfs_set_bitrange(vol->bitmap,location,count,0);
  563.     return error;
  564. }
  565.  
  566. /*
  567.  * Local variables:
  568.  * c-file-style: "linux"
  569.  * End:
  570.  */
  571.  
  572.  
  573.